#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize);
void quickSort(int* arr, int left, int right, int Kth);
inline void swap(int* arr, int idx1, int idx2);

int main()
{
	return 0;
}

int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
{
	int* res = malloc(k * sizeof(int)); *returnSize = k;
	srand(time(NULL));
	quickSort(arr, 0, arrSize, k);

	for (int i = 0; i < k; i++) res[i] = arr[i];
	return res;
}

void quickSort(int* arr, int left, int right, int Kth)
{
	int pivot = left + rand() % (right - left);
	int pivot_val = arr[pivot];

	/* [0, lt) [lt, gt) [gt, end) */
	int lt = 0, eq = 0, gt = right;
	while (eq < gt) {
		int sub = arr[eq] - pivot_val;
		if		(sub > 0) swap(arr, --gt, eq);
		else if (sub < 0) swap(arr, lt++, eq++);
		else eq++;
	}

	if (lt > Kth) quickSort(arr, left, lt, Kth);
	if (gt < Kth) quickSort(arr, gt, right, Kth);
}

void swap(int* arr, int idx1, int idx2)
{
	int temp = arr[idx1];
	arr[idx1] = arr[idx2];
	arr[idx2] = temp;
}
